1905D - Cyclic MEX - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define rep(i,a,b) for (int i = a; i < b; i++)
#define each(i, k, n) for (int i = k;i<=n;i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define endl '\n'
#define f first
// #define s second
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1000000007
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define N 1e5
ll mex(vl &a,ll i){
    set <ll> s(a.begin(),a.begin()+i+1);
    ll ans = 0;
    while(s.count(ans)){
        ans++;
    }
    return ans;
}
void solve(){
    ll n;
    cin >> n;
    vl v(n);
    rep(i,0,n){
        cin >> v[i];
    }
    vl a;
    ll i = 0;
    while(i<n && v[i]!=0){
        i++;
    }
    ll j = i;
    rep(k,0,n){
        a.pb(v[j%n]);
        j++;
    }
    // rep(i,0,n){
    //     cout << a[i] << " ";
    // }
    // cout << endl;
    vl less(n);
    stack <ll> s;
    vl dp(n,n);
    s.push(0);
    rep(i,1,n){
        while(s.size() && a[i] < a[s.top()]){
            s.pop();
        }
        less[i] = s.top();
        s.push(i);
    }
    // rep(i,1,n){
    //     cout << less[i] << " ";
    // }
    // cout << endl;
    // rep(i,0,s.size()){
    //     cout<<s.top() << " ";
    //     s.pop();
    // }
    rep(i,1,n){
        dp[i] = dp[less[i]]  + (i-less[i])*a[i];
    }
    ll ans = n;
    each(i,1,n-1){
        ans = max(ans,dp[i]);
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
        cout<<endl;
    }
    return 0;
}